package top.ivansong92.example.leetcode.learning.data.struct.array;


import org.junit.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class TestExample4 {

    @Test
    public void test1() {
        //System.out.println(removeDuplicates(new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3}));
        System.out.println(singleNonDuplicate(new int[]{1,1,2,3,3,4,4,8,8}));
    }

    /**
     * 540. 有序数组中的单一元素
     * @param nums
     * @return
     */
    public int singleNonDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int len = nums.length;
        if (len % 2 == 0) {
            return -1;
        }

        for(int i = 0; i < len; i += 2) {
            if (i + 1 < len && nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        return nums[len - 1];
    }

    /**
     * 135. 分发糖果
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }
        int len = ratings.length;
        if (len == 1) {
            return 1;
        }
        int[] candyArray = new int[len];
        Arrays.fill(candyArray, 1);
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyArray[i] = candyArray[i - 1] + 1;
            }
        }
        for(int i = len - 2; i >= 0; i --) {
            if (ratings[i] > ratings[i + 1] && candyArray[i] <= candyArray[i + 1]) {
                candyArray[i] = candyArray[i + 1] + 1;
            }
        }

        int res = 0;
        for(int c : candyArray) {
            res += c;
        }
        return res;
    }
    @Test
    public void testluckyNumbers() {
        //System.out.println(removeDuplicates(new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3}));
        System.out.println(luckyNumbers(new int[][]{{3,6},{7,1},{5,2},{4,8}}));
    }

    /**
     * 1380. 矩阵中的幸运数
     * @param matrix
     * @return
     */
    public List<Integer> luckyNumbers (int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return Collections.emptyList();
        }
        int m = matrix.length;
        int n = matrix[0].length;
        if (m == 1 && n == 1) {
            return Collections.singletonList(matrix[0][0]);
        }

        List<Integer> res = new ArrayList<>();
        int[] min = new int[m];
        for (int i = 0; i < m; i++) {
            int[] array = matrix[i];
            int minVal = Integer.MAX_VALUE;
            int minIdx = 0;
            for (int j = 0; j < array.length; j++) {
                if (minVal > array[j]) {
                    minVal = array[j];
                    minIdx = j;
                }
            }
            min[i] = minIdx;
        }

        for (int j = 0; j < n; j++) {
            int max = Integer.MIN_VALUE;
            int maxIdx = 0;
            for (int i = 0; i < m; i++) {
                if (matrix[i][j] > max) {
                    max = matrix[i][j];
                    maxIdx = i;
                }
            }

            if (min[maxIdx] == j) {
                res.add(max);
            }
        }
        return res;
    }

    /**
     * 31. 下一个排列
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }

        int len = nums.length;
        if (len == 2) {
            swap(nums, 0, 1);
            return;
        }

        for (int i = len - 2; i >= 0; i --) {
            if (nums[i] >= nums[i + 1]) {
                continue;
            }
            int val = nums[i];
            int idx = 0;
            for(int j = len - 1; j >= i + 1; j --) {
                if (nums[j] > val) {
                    idx = j;
                    break;
                }
            }
            swap(nums, idx, i);
            reverse(nums, i + 1, len - 1);
            return;
        }
        reverse(nums, 0, len - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void reverse(int[] nums, int start, int end) {
        int left = start, right = end;
        while (left < right) {
            swap(nums, left, right);
            left ++;
            right --;
        }
    }

    /**
     * 面试题 16.06. 最小差
     * @param a
     * @param b
     * @return
     */
    public int smallestDifference(int[] a, int[] b) {
        if (a == null || a.length == 0 || b == null || b.length == 0) {
            return -1;
        }

        Arrays.sort(a);
        Arrays.sort(b);
        int a1 = 0, b1 = 0, res = Integer.MAX_VALUE;
        while (a1 < a.length && b1 < b.length) {
            int tmp = a[a1] - b[b1];
            if (tmp == 0) {
                return 0;
            } else if (tmp < 0) {
                res = Math.min(res, tmp == Integer.MIN_VALUE ? Integer.MAX_VALUE : tmp);
                a1 ++;
            } else {
                res = Math.min(res, tmp);
                b1 ++;
            }
        }
        return res;
    }

    @Test
    public void testsubarraySum() {
        //System.out.println(removeDuplicates(new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3}));
        System.out.println(subarraySum(new int[]{-1, -1, 1}, 0));
    }

    /**
     * TODO
     * 560. 和为 K 的子数组
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0] == k ? 1 : 0;
        }
        Map<Integer, AtomicInteger> sumMap = new HashMap<>();
        sumMap.put(0, new AtomicInteger(1));
        int sum = 0, res = 0;
        for(int i = 0; i < len; i ++) {
            sum += nums[i];
            AtomicInteger count = sumMap.get(sum - k);
            if (count != null) {
                res += count.get();
            }
            sumMap.computeIfAbsent(sum, e-> new AtomicInteger(0)).incrementAndGet();
        }
        return res;
    }

    /**
     * todo
     * 剑指 Offer 49. 丑数
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int idx2 = 0, idx3 = 0, idx5 = 0;
        for(int i = 1; i < n; i ++) {
            int a2 = dp[idx2] * 2, a3 = dp[idx3] * 3, a5 = dp[idx5] * 5;
            dp[i] = Math.min(a2, Math.min(a3, a5));
            if (dp[i] == a2) {
                idx2 ++;
            }
            if (dp[i] == a3) {
                idx3 ++;
            }

            if (dp[i] == a5) {
                idx5 ++;
            }
        }
        return dp[n-1];
    }

    /**
     * 717. 1比特与2比特字符
     * @param bits
     * @return
     */
    public boolean isOneBitCharacter(int[] bits) {
        if (bits == null || bits.length == 0) {
            return false;
        }

        int len = bits.length;
        if (len == 1) {
            return bits[0] == 0;
        }

        if (bits[len - 1] == 1) {
            return false;
        }

        int idx = 0;
        while (idx <= len - 1) {
            int val = bits[idx];
            if (val == 0) {
                if (idx == len - 1) {
                    return true;
                }
                idx ++;

            } else {
                idx += 2;
            }
        }
        return false;
    }

    /**
     * 532. 数组中的 k-diff 数对
     * @param nums
     * @param k
     * @return
     */
    public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length < 2 || k < 0) {
            return 0;
        }

        Map<Integer, AtomicInteger> map = new HashMap<>();
        for (int n : nums) {
            map.computeIfAbsent(n, e -> new AtomicInteger(0)).incrementAndGet();
        }

        int res = 0;
        for (Map.Entry<Integer, AtomicInteger> entry : map.entrySet()) {
            if (k == 0) {
                int count = entry.getValue().get();
                if (count > 1) {
                    res ++;
                }
            } else {
                if (map.get(k + entry.getKey()) != null) {
                    res ++;
                }
            }
        }
        return res;
    }

    /**
     * 35. 搜索插入位置
     * https://leetcode.cn/problems/search-insert-position/
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int len = nums.length;

        int start = 0, end = len - 1, plus = 0, mid = 0;

        if (len == 1) {
            plus = nums[start] - target;
            return plus < 0 ? 1 : 0;
        }

        if (target <= nums[start]) {
            return 0;
        }

        if (target > nums[end]) {
            return len;
        }

        while (start < end) {
            plus = nums[start] - target;
            if (plus == 0) {
                return start;
            }

            plus = nums[end] - target;
            if (plus == 0) {
                return end;
            }

            if (end - start == 1) {
                return end;
            }

            mid = (start + end) / 2;
            plus = nums[mid] - target;
            if (plus == 0) {
                return mid;
            } else if (plus < 0) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return mid;
    }

    @Test
    public void testSearchInsert() {
        //System.out.println(removeDuplicates(new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3}));
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 2));
    }

    /**
     * 1480. 一维数组的动态和
     * https://leetcode.cn/problems/running-sum-of-1d-array/
     * @param nums
     * @return
     */
    public int[] runningSum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int[] res = new int[nums.length];
        res[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res[i] = res[i - 1] + nums[i];
        }
        return res;
    }

    /**
     * 剑指 Offer 03. 数组中重复的数字
     * TODO ：原地翻转
     * https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
     * @param nums
     * @return
     */
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for ( int i = 1; i < nums.length; i ++) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
            }
        }
        return -1;
    }

    /**
     * 169. 多数元素
     * https://leetcode.cn/problems/majority-element/?favorite=ex0k24j
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        Map<Integer, AtomicInteger> numCounter = new HashMap<>();
        int selfLen = nums.length / 2 + nums.length % 2;
        for(int val : nums) {
            AtomicInteger counter = numCounter.computeIfAbsent(val, e-> new AtomicInteger(0));
            int after = counter.addAndGet(1);
            if (after >= selfLen) {
                return val;
            }
        }
        return Integer.MIN_VALUE;
    }
}
